package com.wl2o2o.leetcode;

/**
 * 给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
 * 你应当 保留 两个分区中每个节点的初始相对位置。
 *
 * @Author <a href="https://github.com/wl2o2o">程序员CSGUIDER</a>
 * @From <a href="https://wl2o2o.github.io">CSGUIDER博客</a>
 * @CreateTime 2024/4/20
 */

public class SeparateList86 {
    public ListNode partition(ListNode head, int x) {
        // 创建两个大小链表，最后链接两者即可
        ListNode little = new ListNode(0);
        ListNode big = new ListNode(0);
        ListNode cur = head;
        ListNode littleHead = little;
        ListNode bigHead = big;

        while(cur != null) {
            if (cur.val < x) {
                littleHead.next = cur;
                littleHead = littleHead.next;
            } else {
                bigHead.next = cur;
                bigHead = bigHead.next;
            }
            cur = cur.next;
        }
        // 将链表尾部指向null，否则会出现：Found Cycle
        bigHead.next = null;
        // 小链表尾部链接大链表首部
        littleHead.next = big;

        // 返回
        return little;
    }
}
